МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІСЬКА ПОЛІТЕХНІКА»
Кафедра ІСМ
Звіт
До лабораторної роботи №3
З дисципліни:
«Методи та системи штучного інтелекту»
На тему:
«Алгоритми обходу дерев»
Львів-2017
Мета роботи: полягає у вивченні алгоритмів обходу дерев та застосування їх для запису та обчислення виразів у спеціальних (польських) нотаціях.
Теоретичні відомості
Існує багато задач, які можна моделювати використовуючи деревовидні структури. Поширеною є така загальна постановка задачі: виконати задану операцію D з кожною вершиною дерева. Тут D розглядається як параметр більш загальної задачі відвідування всіх вершин, або, як кажуть, обходу дерева. Якщо розглядати цю задачу як єдиний послідовний процес, то окремі вершини відвідуються у деякому визначеному порядку і можуть вважатись розташованими одна за однією, у лінійному порядку. Опис багатьох алгоритмів істотно спрощується, якщо можна говорити про наступну вершину дерева, маючи на увазі деяке упорядкування.
Існує три принципи впорядкування вершин, які природно випливають із структури дерева. Як і саму деревовидну структуру, їх зручно виразити за допомогою рекурсії. Обходи:
Зверху вниз або обхід у прямому порядку (preorder): R, A, B –тобто відвідати корінь до відвідування піддерев;
Зліва направо або обхід у внутрішньому порядку (inorder): A, R, B;
Знизу вверх або обхід у зворотному порядку (postorder): A, B, R - тобто відвідати корінь після відвідування піддерев.
Прямий польський запис відповідає обходу дерева виразу зверху внизу (префіксна форма запису виразу). Правило обчислення значення виразу у прямому польському записі описується таким алгоритмом. Проглядається справа наліво і виділяються два операнди разом із знаком операції, який їм передує. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.
Обернений польський запис відповідає обходу дерева знизу вверх (постфіксна форма запису). Правило обчислення значення виразу в оберненому польському записі описується таким алгоритмом. Вираз проглядається зліва направо, виділяються два операнди разом із знаком операції, яка стоїть після них. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записується на місце вилучених символів.
Завдання лабораторної роботи:
Виконати обхід заданого дерева зверху донизу, знизу доверху та зліва направо. Дерево може задаватись списками вершин або матрицею суміжності. Програма повинна дозволяти здійснювати обхід, починаючи з кореневої вершини.
Для довільного алгебраїчного виразу, що містить операції додавання, віднімання, множення та ділення та логічного виразу з операціями заперечення, кон’юнкції та диз’юнкції побудувати відповідні пряму та обернену польські записи.
Обчислити значення алгебраїчного та логічного виразів, записаних у прямій та оберненій польських нотаціях.
Результати виконання роботи:
package PHSHI.Lab3;
import java.util.Scanner;
public class ObchPol {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
System.out.println("Введіть вираз: ");
String s=scanner.next();
System.out.println("Виберіть тип польської нотації:\n 1.Пряма\n 2.Обернена");
int n=scanner.nextInt();
switch (n){
case 1:Pryam(s); break;
case 2:Obern(s); break; } }
static void Obern(String s) {
String copy=s;
String s2="";
for(int i=0;i<s.length();i++)
s2+=copy.substring(s.length()-(i+1),s.length()-i);
Pryam(s2); }
static void Pryam(String s) {
String copy=s;
String sub;
boolean flag=false;
int r=0,indx=0,d=0;
while(copy.length()!=1) {
for(int i=0;i<copy.length();i++)
if(copy.charAt(i)=='+'||copy.charAt(i)=='-'||copy.charAt(i)=='/'||copy.charAt(i)=='*') {indx=i; break;}
sub=copy.substring(indx-2,indx+1);
if(sub.charAt(2)=='+')
...
